Intersection of Two Linked Lists

问题描述（难度简单-160）

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

Example 1:

Example 2:

Example 3:

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

方法一：using hash

package P160;

import AddTwoNumbers.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 通过set的方式实现，需要占用额外的空间
 * 时间复杂度O(M+N)
 * 空间复杂度O(M)/O(N)
 * @autor yeqiaozhu.
 * @date 2019-10-10
 */
public class UsingSet {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB==null) {
            return null;
        }
        ListNode a=headA;
        ListNode b=headB;
        Set<ListNode> aSet=new HashSet<>();
        while (a!=null){
            aSet.add(a);
            a=a.next;
        }
        //遍历一下
        while (b!=null){
            if (aSet.contains(b)) {
                return b;
            }
            b=b.next;
        }
        return null;
    }
}

方法二：using two pointer

双指针遍历，其中一个链表遍历到结尾之后从另一个链表的开头开始遍历，时间复杂度O(M+N)，空间复杂度O(1)。

package P160;

import AddTwoNumbers.ListNode;
import CommonUtils.ListNodeUtils;

/**
 * 时间复杂度O(M+N)
 * 空间复杂度O(1)
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB==null) {
            return null;
        }
        ListNode a=headA;
        ListNode b=headB;
        //如果同时到达尾部 没有交点直接返回null
        while (a!=b){
            //a一遍循环结束没有找到交点 继续从b开头节点开始往下走
            a=a==null?headA:a.next;
            //b一遍循环结束没有找到交点 继续从a开头节点开始循环 最后一定会遇到交点的
            b=b==null?headB:b.next;
        }
        return a;
    }

    public static void main(String[] args) {
        ListNode listNodeA=ListNodeUtils.createListNode(4,1);
        ListNode listNodeB=ListNodeUtils.createListNode(4,2);

        new Solution().getIntersectionNode(listNodeA,listNodeB);
    }
}

总结

双指针的方式比较巧妙，注意需要在遍历到尾部的时候重新遍历另一个链表。